/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /*public TreeNode deleteNode(TreeNode root, int key) {

    }*/
    public TreeNode deleteNode(TreeNode root, int key) {
        //先找到这个结点再说。如果找不到，直接返回原来的树
        TreeNode workNode = root;    //工具结点
        TreeNode targetNode = null;  //找到的该结点
        while (workNode != null) {
            if (key < workNode.val) {
                workNode = workNode.left;
            } else if (key > workNode.val) {
                workNode = workNode.right;
            } else { //root.val == key
                targetNode = workNode;  //已经找到该节点
                break;
            }
        }
        if (targetNode == null) {    //二叉树根本没有该结点，直接返回原本的树即可
            return root;
        }
        //情况一：该节点是叶结点,直接删除
        if (targetNode.left==null && targetNode.right==null){
            if (targetNode.val == root.val){    //边界检查：根节点就是叶子结点，直接return null
                return null;
            }
            deleteLeaf(root,targetNode);
            return root;
        }
        //情况二：如果该节点有右结点，将该节点的后继结点(记为successor)提到该节点的位置进行覆盖，并递归删除
        if (targetNode.right!=null){
            TreeNode successor = findSuccessor(targetNode);
            coverNode(targetNode,successor);
            targetNode.right = deleteNode(targetNode.right, successor.val); //递归删除
        }else if (targetNode.right==null && targetNode.left!=null){ //情况三：如果该节点只有左结点而没有右结点，使用该节点的前驱结点（记为predecessor）提到该节点的位置进行覆盖。
            TreeNode predecessor = findPredecessor(targetNode);
            coverNode(targetNode,predecessor);
            targetNode.left =  deleteNode(targetNode.left, predecessor.val); //递归删除
        }

        return root;
    }

    //覆盖结点. oriNode指要被覆盖的结点，newNode指代替它的结点
    private  void coverNode(TreeNode oriNode, TreeNode newNode) {
        oriNode.val = newNode.val;
    }

    //直接删除叶结点
    private  void deleteLeaf(TreeNode root, TreeNode targetNode) {
        TreeNode workNode = root;    //工具结点
        while (true){
            if (targetNode.val < workNode.val){
                if (workNode.left.val!= targetNode.val){
                    workNode = workNode.left;
                }else {
                    workNode.left = null;   //如果相等则删除该结点
                    return;
                }
            }else {
                if (workNode.right.val!= targetNode.val){
                    workNode = workNode.right;
                }else {
                    workNode.right = null;   //如果相等则删除该结点
                    return;
                }
            }
        }
    }

    private  TreeNode findSuccessor(TreeNode node) {
        if (node.right == null) {  //如果没有右结点，该节点的successor肯定在它上面，所以用该方法是找不到的。
            return null;
        }
        node = node.right;
        //下面的代码其实就是调用findMin方法找最小结点
        while (true){
            if (node.left != null) {
                node = node.left;
            }else {
                break;
            }
        }
        return node;
    }

    private  TreeNode findPredecessor(TreeNode node) {
        if (node.left == null) {
            return null;
        }
        node = node.left;
        //下面的代码其实就是调用findMax方法找最大结点
        while (true){
            if (node.right != null) {
                node = node.right;
            }else {
                break;
            }
        }
        return node;
    }
}




//leetcode submit region end(Prohibit modification and deletion)
